package test.n00000;

public class Problem00051 {
    public static void main(String[] args) {
        println("babad");
        println("cbbd");
        println("bb");
        println("babad");
        println("aacabdkacaa");
    }

    public static void println(String s) {
        Solution ss = new Solution();
        System.out.println(s + "," + ss.longestPalindrome(s));
    }

    public static class Solution {
        /**
         * 给你一个字符串 s，找到 s 中最长的回文子串。
         * <p>
         * 解题方法:(暴力法+中心扩散)
         * 取字符串中间的字符，依次左右定位，判断最大回文
         *
         * @param s
         * @return
         */
        public String longestPalindrome(String s) {
            int maxLen = 1;
            int begin = 0;

            for (int i = 1; i < s.length(); i++) {
                int oddLen = longestPalindrome(s, i, i);
                int evenLen = longestPalindrome(s, i - 1, i);

                if (maxLen >= oddLen && maxLen >= evenLen) {
                    continue;
                }

                maxLen = Math.max(oddLen, evenLen);
                begin = i - maxLen / 2;
            }
            return s.substring(begin, begin + maxLen);
        }

        public static int longestPalindrome(String s, int leftPos, int rightPos) {
            while (leftPos >= 0 && rightPos < s.length()) {
                if (s.charAt(leftPos) == s.charAt(rightPos)) {
                    leftPos--;
                    rightPos++;
                } else {
                    break;
                }
            }

            return rightPos - leftPos + 1 - 2;
        }
    }
}
